Facetization is the solution for n-squared problems. N-squared problems require each vertex or segment to be compared to every other vertex or segment. So for n segments, there are n² operations to be performed. If there are 100 segments, there are 10,000 operations, which would not warrant facetizing because 10,000 mathematical operations can be performed relatively quickly with today’s computers. But 1,000 or 10,000 segments would require 1,000,000 or 100,000,000 operations respectively, so facetization in each of these cases would be worth using.

OpenCities Map helps to avoid these very large problems by automatically breaking a fence into a grid of cells. If 10 columns and 10 rows were specified, the fence would break down into 100 cells and would perform the command 100 times, once for each cell.

In theory 10,000 lines would result in 100 fence operations against 100 lines each for a total of 1,000,000 operations (100 fences times 100 lines times 100 lines) instead of 100,000,000 operations (10,000 lines times 10,000 lines). Since many lines typically overlap multiple cells in the grid, the operation is usually less efficient than the example. However, it is not unusual to see 10 to 30 times improvement in performance.

Depending upon the type of data, facetization can actually require longer processing times. This may occur if the data contains long irregular linear elements that cross a great number of cells in the grid, or if a very large number of cells is specified. When to facetize and by how much depends upon the computer’s speed and available memory. Test a number of combinations to determine an optimal level of facetization for the computer and datasets.

Besides improving the performance of many topology cleanup operations, facetization can also significantly reduce the amount of required memory. For example, to segment two megabytes of linear elements, require 10 megabytes of virtual memory. However, to facetize 10 columns by 10 rows, only one megabyte or less of memory is required.